A public key cryptography system is made up of a collection of users, each having his own encryption and decryption keys. In one such system, known as the RSA system, the encryption key comprises two integers N and e and the decryption key is single integer d. The integers N, d, and e are typically very large integers whose binary representations typically involve several hundred bits. Each user makes his encryption key available to the other users while keeping his decryption key secret.
In this system, N is an integer which is the product of two carefully selected large primes p and q and e is an integer such that its greatest common divisor with (p-1)(q-1) is one [gcd {e,(p-1)(q-1)]=[. Finally, d is calculated by solving the linear congruence EQU de=1 (mod(p-1)(q-1))
If a user A wishes to communicate a numerically coded message M to another user B he calculates the ciphertext K=M.sup.e (mod N)(0.ltoreq.K&lt;N, 0.ltoreq.M&lt;N) where e and N form the encryption key for user B. To determine the plaintext M from the ciphertext K, B uses the decryption key d to calculate EQU M=K.sup.d (mod N) (0.ltoreq.M&lt;N)
Thus, both the encryption and decryption operations involve repeated modular multiplications where the modulus N has a representation involving hundreds of bits.
As a result, great effort has been expended in the field of cryptography to find fast and inexpensive ways to do modular multiplication (see, e.g., E.F. Brickell "A Survey of Hardware Implementations of RSA" presented at CRYPTO'89, Santa Barbara, Calif., August 1989; S.R. Dusse et al, "A Cryptographic Library for the Motorola DSP 56000" EuroCrypt 90--Abstracts, May 21-24, 1990, Scanticon Arhus, Denmark, pp. 213-217; H. Orup et al, "VICTOR, An Efficient RSA Hardware Implementation" Eurocrypt 90--Abstracts, May 21-24 1990 Scanticon, Arhus, Denmark, pp. 219-227).
A systolic array of cells for performing ordinary (i.e. not modular) multiplication of large integers has been proposed by Atrubin (see, A.J. Atrubin, "A One-Dimensional Real Time Iterative Multiplier", IEEE Trans. on Electronic Computers, Vol. 14, 1965, pp. 394-399). Two positive integers to be multiplied are represented in binary. They are fed serially to the first cell of the array, least significant bit first. The product is supplied by the first cell, least significant bit first, without delay. The time required to obtain the product is linear with the length of the product. The structure of each cell in Atrubin's array is very simple and the array utilizes no long distance communications, i.e., each cell communicates only with its neighbors. Thus, a very high clock rate is possible.
It is an object of the present invention to provide a systolic array of cells which can be utilized in combination with Atrubin's array to perform repetitive modular multiplications of the type utilized in the above-described public key cryptographic systems.
As is shown below the inventive systolic array utilizes the modular reduction system proposed by Montgomery (see, P.L. Montgomery, "Modular Multiplication Without Trial Division", Math. of Computation, Vol. 44, 1985, pp. 519-521).
The modular reduction system of Montgomery may be understood as follows. Let the modulus N be an odd integer. Let n be the number of bits in the binary representation of N i.e. 2.sup.n-1 &lt;N&lt;2.sup.n. Let R=2.sup.n. Let x be the image of the integer where x=xR(mod N). A binary representation of an image has at most n bits and it may exceed N, but it is nonnegative.
In the Montgomery modular multiplication system, modular operations are done with images. For example, suppose one wants to multiply two numbers x and y to obtain a product z=xy(mod N). In the Montgomery system this is done by multiplying x and y to obtain M=xy=xyR.sup.2 (mod N)=zR.sup.2 (Mod N)=zR(Mod N). Note that M has at most 2n bits and z is non-negative and has at most n bits.
In order to obtain z from M it is necessary to divide M by R and in order to obtain z from z it is necessary to divide again by R. This modular division by R is known as modular reduction.
Thus, it is a further object of the present invention to provide a systolic array of cells to perform the above-described modular reduction operation and to utilize the systolic array to perform repeated modular multiplications in a cryptographic system.